# coding=utf-8


class DFAFilter(object):
    def __init__(self):
        self.keyword_chains = {}
        self.delimit = '\x00'

    def add(self, keywords):
        for keyword in keywords:
            keyword = keyword.lower()
            chars = keyword.strip()
            if not chars:
                return
            level = self.keyword_chains
            for i in range(len(chars)):  # 'sadas'
                if chars[i] in level:
                    level = level[chars[i]]
                else:
                    if not isinstance(level, dict):
                        break
                    last_level = {}
                    last_char = ''
                    for j in range(i, len(chars)):
                        level[chars[j]] = {}
                        last_level, last_char = level, chars[j]
                        level = level[chars[j]]
                    last_level[last_char] = {self.delimit: 0}
                    break
                if i == len(chars) - 1:
                    level[self.delimit] = 0


    def filter(self, message, repl="*"):
        message = message.lower()
        ret = []
        start = 0
        while start < len(message):
            level = self.keyword_chains
            step_ins = 0
            for char in message[start:]:
                if char in level:
                    step_ins += 1
                    if self.delimit not in level[char]:
                        level = level[char]
                    else:
                        ret.append(repl * step_ins)
                        start += step_ins - 1
                        break
                else:
                    ret.append(message[start])
                    break
            else:
                ret.append(message[start])
            start += 1

        return ''.join(ret)

    def valid(self, message):
        message = message.lower()
        start = 0
        while start < len(message):
            level = self.keyword_chains
            step_ins = 0
            for char in message[start:]:
                if char in level:
                    step_ins += 1
                    if self.delimit not in level[char]:
                        level = level[char]
                    else:
                        return message[start:start + step_ins]
                else:
                    break
            start += 1


if __name__ == '__main__':
    keywords = ['十大科技大厦空萨顶顶从间的哈桑', '萨顶顶从', '阿斯顿', '撒旦从']
    dfa = DFAFilter()

    dfa.add(keywords)
    result =dfa.filter('撒撒旦撒撒旦从现场撒打算现在才')
    print(result)
